package sword.chapter12Sort;

/**
 * 计数排序
 * 2 2 1 3 4 3 5
 * 1 2 2 3 3 4 5
 *
 * 1. 记录最小值 最大值
 * 2. 创建最小值到最大值之间的数组counts，统计每个数出现次数
 * 3. 从最小值开始遍历，在counts中取值并更新值
 *
 * 要点
 * 1. 最小值 最大值区间确定
 *
 * @author K
 * @date 2022-01-11 21:52
 */
public class CountSort {

    public static int[] sort(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        int[] counts = new int[max - min + 1];
        for (int num : nums) {
            counts[num - min]++;
        }

        int i = 0;
        for (int num = min; num <= max; num++) {
            while (counts[num - min] > 0) {
                nums[i++] = num;
                counts[num - min]--;
            }
        }

        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 1, 3, 4, 3, 5};
        int[] result = sort(nums);
        System.out.println();
    }
}
